package com.xiaoyu.string;

import java.util.HashMap;
import java.util.TreeMap;

/**
 * @program: DS_and_A
 * @description: 力扣13,罗马数字转整数
 * I             1
 * V             5
 * X             10
 * L             50
 * C             100
 * D             500
 * M             1000
 *
 * I可以放在V(5) 和X(10) 的左边，来表示 4 和 9。
 * X可以放在L(50) 和C(100) 的左边，来表示 40 和90。
 * C可以放在D(500) 和M(1000) 的左边，来表示400 和900。
 *
 * 符合罗马数字书写规则，不会出现跨位等情况。
 * IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
 *
 * @author: YuWenYi
 * @create: 2021-04-24 08:23
 **/
public class RomanToInt {

    private TreeMap<Character,Integer> numMapping = new TreeMap<>();
    public void initMapping(){
        numMapping.put('I',1);
        numMapping.put('V',5);
        numMapping.put('X',10);
        numMapping.put('L',50);
        numMapping.put('C',100);
        numMapping.put('D',500);
        numMapping.put('M',1000);
    }
    /*  规律总结:

        总体而言,由于罗马数字不能进行跨位操作,因此我发现,从右往左看,当右边的数字大于左边的数字.
        那么,就需要右边的数字减去左边的数字,从而得到结果,不用担心跨位比较还出现右边比左边大,
        仔细想想个位怎么也不会大于十位,以此类推

        有了这个思路,就简单了!
        循环遍历字符串数组,如果右边的数字大于左边,--> res = res + 右(当前数字) - 左,此时由于"左"的数字已经用掉了,被减去了,因此需要i--操作进一位
                          否则 --> res = res + 当前数字
        与此同时,由于有--的操作,因此会出现数组越界问题,所以我使用 if (i != 0) ,去防止这种情况,
        同时又需要补偿i=0的情况,因此直接 res += numMapping.get(chars[i]);
    */
    public int romanToInt(String s) {
        initMapping();
        char[] chars = s.toCharArray();
        int res = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            if (i != 0) {    //防止数组越界
                if (numMapping.get(chars[i]) > numMapping.get(chars[i - 1])) {
                    res = res + numMapping.get(chars[i]) - numMapping.get(chars[i - 1]);
                    i--;
                }else {
                    res += numMapping.get(chars[i]);
                }
            }else {   //如果是偶数个字符,则不会进入到这个else里面
                res += numMapping.get(chars[i]);
            }
        }
        return res;
    }

    /*
    * 大佬解法:
    * int sum = 0;
        int preNum = getValue(s.charAt(0));
        for(int i = 1;i < s.length(); i ++) {
            int num = getValue(s.charAt(i));
            if(preNum < num) {
                sum -= preNum;
            } else {
                sum += preNum;
            }
            preNum = num;
        }
        sum += preNum;
        return sum;
    }

    private int getValue(char ch) {
        switch(ch) {
            case 'I': return 1;
            case 'V': return 5;
            case 'X': return 10;
            case 'L': return 50;
            case 'C': return 100;
            case 'D': return 500;
            case 'M': return 1000;
            default: return 0;
        }
    }
    * */

    public static void main(String[] args) {
        RomanToInt romanToInt = new RomanToInt();
        String roman = "MCMXCIV";   //58   "MCMXCIV" -->1994

        int num = romanToInt.romanToInt(roman);
        System.out.println("num-->"+num);
    }

}
